package Tree.Heap;

/*
    堆有大根堆和小根堆
    大根堆适合求最小K个元素的问题，小根堆适合求TOP K 的问题
    这里我们拿大根堆举例，采用数组存储堆
 */
public class BigRootHeap {
}

class Heap {
    private int[] a;
    private int capacity;//堆的容量
    private int count;//堆中已有元素的个数

    public Heap(int capacity) {
        a = new int[capacity];
        this.capacity = capacity;
        count = 0;
    }

    private void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public void insert(int data) {
        if (count == capacity) return;
        count++;
        a[count] = data;//把元素放入末尾，然后进行堆化
        //数组的第一个位置不放元素。为了方便用i/2来算得父节点
        int i = count;
        while (i / 2 > 0 && a[i] > a[i / 2]) {
            swap(a, i, i / 2);
            i = i / 2;
        }
    }

    /*  删除根
        思想：把根删除后把最后一个节点补到根的位置，然后再从上往下堆化。
        这里说一下为什么要用最后一个元素来补到根的位置。
        因为如果用根的孩子直接补的话，很有可能到最后一层的时候，一个中间的叶子节点补了上去，
        导致整棵树的结构不再是完全二叉树，这样就不符合堆的定义了
     */
    public void removeMax() {
        if (count == 0) return;
        a[1] = a[count];//那最后一个元素先补到根的位置
        count--;
        heapify(a, count, 1);
    }

    private void heapify(int[] a, int n, int i) {
        while (true) {
            int maxPos = i;
            if (i * 2 <= n /*i有左孩子*/ && a[i] < a[i * 2]) maxPos = i * 2;
            if (i * 2 + 1 <= n /*i有右孩子*/ && a[maxPos] < a[i * 2 + 1]) maxPos = i * 2 + 1;
            //如果这次没有找到需要交换的孩子，说明现在已经符合大根堆的要求了，退出循环
            if (maxPos == i) break;
            swap(a, i, maxPos);
            i = maxPos;
        }
    }
    /*  看完了删除根，进一步可以推出删除任意元素，其实和删除根差不多
        依旧是用末尾元素顶替删除元素的位置，不过在这里，如果末尾元素大于删除的元素，
        那就要向上堆化（很好理解吧，因为这个元素大于之前的元素，它一定比孩子都大，但是可能会比父节点大
        所以要向上堆化，来维持大根堆的定义）
        否则就向下堆化
     */
}